Walls and Gates

You are given a m x n 2D grid initialized with these three possible values.

  1. -1 - A wall or an obstacle.
  2. 0 - A gate.
  3. INF - Infinity means an empty room. We use the value 2^31 - 1 = 2147483647 to represent INF as you may assume that the distance to a gate is less than 2147483647.

Fill each empty room with the distance to its nearest gate. If it is impossible to reach a gate, it should be filled with INF.

For example, given the 2D grid:

  1. INF  -1  0  INF
  2. INF INF INF  -1
  3. INF  -1 INF  -1
  4.   0  -1 INF INF

After running your function, the 2D grid should be:

  1.   3  -1   0   1
  2.   2   2   1  -1
  3.   1  -1   2  -1
  4.   0  -1   3   4

Solution:

  1. public class Solution {
  2.   int[] dx = {-1, 1, 0, 0};
  3.   int[] dy = {0, 0, -1, 1};
  5.   public void wallsAndGates(int[][] rooms) {
  6.     if (rooms.length == 0 || rooms[0].length == 0)
  7.       return;
  9.     int n = rooms.length, m = rooms[0].length;
  11.     for (int i = 0; i < n; i++) {
  12.       for (int j = 0; j < m; j++) {
  13.         if (rooms[i][j] == 0) {
  14.           bfs(rooms, n, m, i, j);
  15.         }
  16.       }
  17.     }
  18.   }
  20.   void bfs(int[][] rooms, int n, int m, int i, int j) {
  21.     Queue<Integer[]> queue = new LinkedList<>();
  22.     queue.add(new Integer[]{i, j});
  23.     queue.add(null);
  25.     int level = 1;
  27.     while (!queue.isEmpty()) {
  28.       Integer[] p = queue.poll();
  30.       if (p != null) {
  31.         for (int k = 0; k < 4; k++) {
  32.           int x = p[0] + dx[k];
  33.           int y = p[1] + dy[k];
  35.           if (x >= 0 && x < n && y >= 0 && y < m && rooms[x][y] > level) {
  36.             rooms[x][y] = level;
  37.             queue.add(new Integer[]{x, y});
  38.           }
  39.         }
  40.       } else if (!queue.isEmpty()) {
  41.         level++;
  42.         queue.add(null);
  43.       }
  44.     }
  45.   }
  46. }